class Solution:
    def longestPalindrome(self, s: str) -> str:
        pre_s = self.preprocess(s)
        max_length = len(pre_s)
        i = 0
        center = 0
        right = 0
        P = [0] * max_length
        while i < max_length:
            # i 如果在右边界里面的话，先用对称点的数据，再进行扩展
            # i 如果在右边界上或者右边界外面，那直接进行扩展
            if i < right:
                mirror = 2 * center - i
                P[i] = min(right - i, P[mirror])

            # 进行中心扩展
            while (
                i + P[i] + 1 < max_length
                and i - P[i] - 1 >= 0
                and pre_s[i + P[i] + 1] == pre_s[i - P[i] - 1]
            ):
                P[i] += 1

            # 更新中心和右边界
            if i + P[i] > right:
                center, right = i, i + P[i]

            i += 1
        res_len = max(P)  # 最大回文半径
        res_center = P.index(res_len)  # 对应的中心位置
        return s[(res_center - res_len) // 2 : (res_center + res_len + 1) // 2]

    def preprocess(self, s: str) -> str:
        # Add boundaries to the string to handle even-length palindromes
        return "#" + "#".join(s) + "#"


s = "baba"
solution = Solution()
result = solution.longestPalindrome(s)
print(f"Test 1: {result}")
